/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\40.组合总和-ii.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-22 14:38:45
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-22 14:48:16
 */
/*
 * @lc app=leetcode.cn id=40 lang=cpp
 *
 * [40] 组合总和 II
 */

// @lc code=start
class Solution {
    private:
        vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> path;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates,path,0,0,target);
        return res;
    }

    void backtrack(vector<int> &candidates, vector<int> &path, int sum, int start, int target)
    {
        if(sum == target)
        {
            res.push_back(path);
        }else if(sum > target)
        {
            return;
        }
        for(int i = start;i < candidates.size() ; i++)
        {
            // 剪枝处理
            if(i > start && candidates[i] == candidates[i-1])
                continue;   
            path.push_back(candidates[i]);
            backtrack(candidates,path,sum+candidates[i],i+1,target);
            path.pop_back();
        }
    }
};
// @lc code=end

